package 每日一题;

import publicClass.ListNode;

import java.util.Stack;

/**
 * 2487. 从链表中移除节点
 * 提示
 * 中等
 * 74
 * 相关企业
 * 给你一个链表的头节点 head 。
 *
 * 移除每个右侧有一个更大数值的节点。
 *
 * 返回修改后链表的头节点 head 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [5,2,13,3,8]
 * 输出：[13,8]
 * 解释：需要移除的节点是 5 ，2 和 3 。
 * - 节点 13 在节点 5 右侧。
 * - 节点 13 在节点 2 右侧。
 * - 节点 8 在节点 3 右侧。
 * 示例 2：
 *
 * 输入：head = [1,1,1,1]
 * 输出：[1,1,1,1]
 * 解释：每个节点的值都是 1 ，所以没有需要移除的节点。
 *
 *
 * 提示：
 *
 * 给定列表中的节点数目在范围 [1, 105] 内
 * 1 <= Node.val <= 105
 */
public class T2487_从链表中移除节点 {

    //使用栈 不断删除站内的元素 直到 栈顶元素大于当前的元素 当前元素才可以入栈
    public ListNode removeNodes(ListNode head) {

        Stack<ListNode> nodeStack = new Stack<>();
        while (head != null) {
            saveNode(nodeStack,head);
            head = head.next;
        }

        //取出栈中元素 重新组成链表
        head = null;
        while (!nodeStack.isEmpty()){
            ListNode node = nodeStack.pop();
            node.next = head;
            head = node;
        }
        return head;
    }

    //将 比较栈顶的值 如果栈顶的值小于node.val 删除栈顶元素 继续比较 直到栈为空或者栈顶元素大于node 将node存入栈
    public void saveNode(Stack<ListNode> nodeStack,ListNode node){

        while (!nodeStack.isEmpty()){

            if (nodeStack.peek().val<node.val) {
                nodeStack.pop();
            }else {
                break;
            }
        }
        nodeStack.add(node);
    }

    public static void main(String[] args) {
        T2487_从链表中移除节点 test = new T2487_从链表中移除节点();
        ListNode listNode1 = new ListNode(5);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(13);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(8);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        test.removeNodes(listNode1);
    }

}
